package 代码随想录.动态规划.b;

import java.util.Arrays;
import java.util.Scanner;

public class a11_01背包理论基础1 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] weight = new int[m];
        int[] value = new int[m];
        for (int i = 0; i < m; i++) {
            weight[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            value[i] = sc.nextInt();
        }
        System.out.println(solution.solve(m, n, weight, value));
    }

    static class Solution {
        /**
         * 物品数量，背包容量，物品占用空间，物品价值
         */
        public int solve(int m, int n, int[] weight, int[] value) {
            int[][] dp = new int[m][n + 1];
            for (int j = weight[0]; j <= n; j++) {
                dp[0][j] = value[0];
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (j - weight[i] >= 0) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }

                }
            }
            for (int i = 0; i < m; i++) {
                System.out.println(Arrays.toString(dp[i]));
            }
            return dp[m - 1][n];
        }
    }
}
